You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or twosteps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

給一個 array cost 紀錄每一步的花費，每次可以前進一步或兩部，只能從 cost 的 index = 0 或 index = 1 開始，找出花費最少的值。

Step

1. costs = [10]，則只有一種方法
2. costs = [10,15] 則有兩種方法，從 index = 0 出發 (10+15) 或從 index = 1 出發 (15)
   

3. costs = [10,15,30] 要走到 30 則有兩種方式
   
   • 從 10 走兩步，從起點走到 10 花費的最少金額在 1 已經算過並放在 dp[0] 中將他和 30 相加
     
   • 從 15 走一步，從起點走到 15 花費的最少金額在 2 已經算過並放在 dp[1] 中將他和 30 相加
     
   • 兩種走法取最小的放入 dp 中代表從起點走到 30 所花費的最少金額
     

4. costs = [10,15,30,5] 要走到 5 則有兩種方式
   • 從 15 走兩步，從起點走到 15 花費的最少金額在 2 已經算過並放在 dp[1] 中將他和 5 相加
     
   • 從 30 走一步，從起點走到 30 花費的最少金額在 3 已經算過並放在 dp[2] 中將他和 5 相加
     
   • 兩種走法取最小的放入 dp 中代表從起點走到 5 所花費的最少金額
     

5. costs = [10,15,30,5,20] 要走到 20 則有兩種方式
   • 從 30 走兩步，從起點走到 30 花費的最少金額在 3 已經算過並放在 dp[2] 中將他和 20 相加
     
   • 從 5 走一步，從起點走到 5 花費的最少金額在 4 已經算過並放在 dp[3] 中將他和 20 相加
     
   • 兩種走法取最小的放入 dp 中代表從起點走到 20 所花費的最少金額
     

6. 已經計算完走到樓梯最後一階為止所要花費的金額，要完全走完樓梯就有兩種方法
   • 從 5 走兩步離開樓梯
     
   • 從 20 走一步離開樓梯
     
   • dp[3], dp[4] 分別紀錄了走到 5 和走到 20 所花費的最少金額，所以可以看出從 5 走兩步離開樓梯金額是最少的。

Coding

var minCostClimbingStairs = function(cost) {
    const dp = [cost[0], cost[1]];

    for(let i = 2; i < cost.length; i++) {
        dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
    }

    return Math.min(dp[dp.length - 1], dp[dp.length - 2]);
};

Time complexity: O(n)